package top.humbleyuan.tree;

import top.humbleyuan.datastructure.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author HumbleYuan
 * @Date 2020/5/19 19:57
 * @Des 树的层次遍历
 */
public class LeetCode_102 {
    public static void main(String[] args) {
        // 递归
        m1();

        // 循环
        m2();
    }


    // 递归
    public static void m1() {
        TreeNode head = new TreeNode(2);
        head.formTree();

        List<List<Integer>> res = new ArrayList<>();
        recursion(head, 0, res);

        System.out.println(res);
    }

    // bfs
    public static void recursion(TreeNode root, int level, List<List<Integer>> res) {
        if(root == null) {
            return;
        }

        if(level == res.size()) {
            res.add(new ArrayList<>());
        }

        res.get(level).add(root.val);

        recursion(root.left, level + 1, res);
        recursion(root.right, level + 1, res);
    }


    // 使用队列循环迭代
    public static void m2() {
        TreeNode head = new TreeNode(2);
        head.formTree();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);

        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> headList = new ArrayList<>();
        headList.add(head.val);

        res.add(headList);

        while(!queue.isEmpty()) {
//           TreeNode curNode = queue.poll();

            Queue<TreeNode> cur = new LinkedList<>();
            ArrayList<Integer> curList = new ArrayList<>();
            while(!queue.isEmpty()) {
                TreeNode curNode = queue.poll();

                if(curNode.left != null) {
                    cur.offer(curNode.left);
                    curList.add(curNode.left.val);
                }

                if(curNode.right != null) {
                    cur.offer(curNode.right);
                    curList.add(curNode.right.val);
                }
            }

            if(curList.size() > 0) {
                res.add(curList);
            }

            queue = cur;
        }

        System.out.println(res);
    }
}
